import java.io.*;

public class B {

    BufferedReader fin;
    PrintWriter fout;

    void openFiles() throws IOException {
        fin = new BufferedReader(new FileReader("B.in"));
        fout = new PrintWriter(new BufferedWriter(new FileWriter("B.out")));
    }

    void closeFiles() throws IOException {
        fin.close();
        fout.close();
    }
    
    int N;
    String result = "";
    int count[];
    
    void input() throws IOException
    {
    	N = Integer.parseInt(fin.readLine());
    	for (int i = 0; i < N; i++)
    	{
    		String s = fin.readLine();
    		result = process(s);
    		fout.println("Case #" + new Integer(i+1).toString() + ": " + result);
       	}
    }
    
    String process(String s)
    {
    	if (s.length() == 1) return (s + "0");
    	
    	String res = "";
    	
    	boolean ok = true;
    	for (int i = 0; i < s.length()-1; i++)
    		if (s.charAt(i) < s.charAt(i+1))
    		{
    			ok = false;
    			break;
    		}
    	
    	if (ok)
    	{
    		int pos = s.length()-1;
    		while (s.charAt(pos) == '0') pos--;
    		s = s.substring(0, pos) + s.substring(pos+1) + s.charAt(pos);
    		
    		for (int i = 0; i < s.length()-1; i++) res = s.charAt(i) + res;
    		res = "0" + res;
    		res = s.charAt(s.length()-1) + res;
    	}
    	else
    	{
    		count = new int[10];
    		for (int i = s.length()-1; i >= 1; i--){
    			count[s.charAt(i) - '0']++;
    			
    			if (s.charAt(i) > s.charAt(i-1)){
    				
    				for (int j = (s.charAt(i-1) - '0')+1; j < 10; j++)
    					if (count[j] > 0)
    					{
    						res = new Integer(j).toString();
    						count[j]--;
    						break;
    					}
    				res = s.substring(0, i-1) + res;
    				count[s.charAt(i-1) - '0']++;
    				for (int j = 0; j < 10; j++)
    					while (count[j] > 0)
    					{
    						res += new Integer(j).toString();
    						count[j]--;
    					}
    				break;
    			}
    		}
    	}
    	
    	return res;
    }
    
    void output()
    {
    }
    
	public static void main(String[] args) throws IOException {
	B myProgram = new B();

        myProgram.openFiles();
        myProgram.input();
        myProgram.output();
        myProgram.closeFiles();
	}

}
